// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-01 23:23
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Tree.TreeArray;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int n, len;
    static int[] lis;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            /*-----确定数组大小-----*/
            n = sc.nextInt();
            len = 1;
            while (len < n) {
                /*-----数组大小设置为第一个大于等于的2^k-----*/
                len *= 2;
            }
            lis = new int[len * 2];
            /*
             为什么使用二维数组记录信息？
             需要记录数据的索引和数据
             */
            int[][] data = new int[n][2];
            for (int i = 0; i < n; i++) {
                data[i] = new int[]{sc.nextInt(), i};
            }
            /*
                数据预处理（排序）
             */
            Arrays.sort(data, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    // 如果元素相同，索引递减；否则元素递增
                    if (o1[0] == o2[0]) {
                        return o2[1] - o1[1];
                    }
                    return o1[0] - o2[0];
                }
            });
            for (int[] s : data) {
                /*-----创建数组之前先询问，根据询问的最大值插入数组-----*/
                int preCnt = query(len, len + s[1] - 1);
                update(s[1] + len, preCnt + 1);
            }
            // 查询所有叶子节点中，LIS最大的元素
            System.out.println(query(len, len + n - 1));
        }
    }

    /**
     * 查询叶子节点中指定区域的最大LIS，创造的树状数组是一棵完全二叉树，start之所以为len是根据完全二叉树的性质
     * 方法的目的是实现当前元素索引到叶子节点开始节点处最大的LIS,从根节点往上走，查询的时间复杂度为O(lgH)
     *
     * @param start
     * @param end
     * @return
     */
    private static int query(int start, int end) {
        // 树状数组中没有元素的时候结果为空
        int result = 0;
        while (start <= end) {
            if (start % 2 == 1) {
                result = Math.max(lis[start], result);
            }
            if (end % 2 == 0) {
                result = Math.max(lis[end], result);
            }
            start = (start + 1) / 2;
            end = (end - 1) / 2;
        }
        return result;
    }

    /**
     * 更新树状数组指定叶子节点的数据，而且同时需要对非叶子节点的数据进行更新
     *
     * @param index
     * @param val
     */
    private static void update(int index, int val) {
        while (index > 0 && val > lis[index]) {
            lis[index] = val;
            index /= 2;
        }
    }
}
